package offer.diff;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author DengYuan2
 * @create 2021-03-09 18:53
 */
public class n_21 {
    public static void main(String[] args) {
        n_21 n = new n_21();
        int[] arr = {1,2,3,4,5};
        n.reOrderArray3(arr);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 我的写法，可以但没必要，类似于下面的方法2
     * 时间复杂度 O(N)，空间复杂度 O(N)
     * @param array
     */
    public void reOrderArray(int[] array) {
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                even.add(array[i]);
            } else {
                odd.add(array[i]);
            }
        }

        int idx = 0;
        for (int i = 0; i < odd.size(); i++) {
            array[idx++] = odd.get(i);
        }
        for (int i = 0; i < even.size(); i++) {
            array[idx++] = even.get(i);
        }
    }

    /**
     * 创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)
     * @param nums
     */
    public void reOrderArray2(int[] nums) {
        // 奇数个数
        int oddCnt = 0;
        for (int x : nums)
            if (!isEven(x))
                oddCnt++;
        int[] copy = nums.clone();
        int i = 0, j = oddCnt;
        for (int num : copy) {
            if (num % 2 == 1)
                nums[i++] = num;
            else
                nums[j++] = num;
        }
    }

    private boolean isEven(int x) {
        return x % 2 == 0;
    }

    /**
     * 冒泡思想，每次都将当前偶数上浮到当前最右边。
     * 时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间
     */
    public void reOrderArray3(int[] nums){
        boolean flag =false;
        for (int i = 0; i < nums.length - 1; i++) {
            flag=false;
            for (int j = 0; j < nums.length-1-i; j++) {
                if (nums[j]%2==0){
                    if (nums[j+1]%2!=0){
                        int tmp = nums[j];
                        nums[j]=nums[j+1];
                        nums[j+1]=tmp;
                        flag=true;
                    }
                }
            }
            if (!flag){
                return;
            }
        }

    }
}
